# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def countPairs(self, root: TreeNode, distance: int) -> int:
        def dfs(node, depth, distance, res):
            if node is None:
                return []
            leftLeaves = dfs(node.left, depth + 1, distance, res)
            rightLeaves = dfs(node.right, depth + 1, distance, res)
            if leftLeaves and rightLeaves:
                for leftLeaf in leftLeaves:
                    for rightLeft in rightLeaves:
                        d = (leftLeaf - depth) + (rightLeft - depth)
                        if d <= distance:
                            res[0] += 1
            leaves = []
            if node.left is None and node.right is None:
                leaves += [depth]

            return leaves + leftLeaves + rightLeaves

        res = [0]

        dfs(root, 0, distance, res)

        return res[0]
